Irregular Parallel Problem

In practice all problems break down at some point to an irregular problem, where the dimensions or connectivity are irregular.

This example shows a typical 'function' that performs 7 sub-tasks. These sub-tasks are inter-dependent.

Sequential Code Solution

The sequential code solution for this problem is very simple

B ComputeB( A a )
{
   B b; C c; D d; E e; F f; G g; H h;

   c = CalcC( a );
   d = CalcD( a );
   e = CalcE( a );
   
   f = CalcF( c, d );
   g = CalcG( c, e );
   h = CalcH( d, e );
   
   b = CalcB( f, g, h );  
   return b;
}

The function ComputeB takes one input and generates a single output. Each of the sub-tasks CalcC..CalcH and CalcB are independent (except for some shared inputs).

Parallel Code Solution

Traditional programming techniques require analysis of the tasks to decide which can be performed in parallel. This is obviously CalcC+CalcD+CalcE and CalcF+CalcG+CalcH.

B ComputeB( A a )
{
   B b; C c; D d; E e; F f; G g; H h;

   Action[] actionsCDE = new Action[3];
   Action[] actionsFGH = new Action[3];
   
   actionsCDE[0] = delegate
   {
      c = CalcC( a );
   }
   actionsCDE[1] = delegate
   {
      d = CalcD( a );
   };
   actionsCDE[2] = delegate
   {
      e = CalcE( a );
   };
   
   actionsFGH[0] = delegate
   {
      f = CalcF( c, d );
   };
   actionsFGH[1] = delegate
   {
      g = CalcG( c, e );
   };
   actionsFGH[2] = delegate
   {
      h = CalcH( d, e );
   };

   Parallel.Invoke( actionsCDE );
   Parallel.Invoke( actionsFGH );
   
   b = CalcB( f, g, h );

   return b;
}

However, the function CalcG doesnt need the output from CalcD, and so could be started and run in 'parallel' as soon as C and E are calculated. (NB. we have not put any stipulation on how long each sub-task takes). Similarly CalcF and CalcH could be started as soon as the inputs are ready.

B ComputeB( A a )
{
   B b; C c; D d; E e; F f; G g; H h;

   Uns tasksComplete[6] = { FALSE };
   
   TaskList tasks = new TaskList();
   tasks.Set( CC, Task.Create( delegate { c = CalcC( a );  } ));
   tasks.Set( DD, Task.Create( delegate { d = CalcD( a );  } ));
   tasks.Set( EE, Task.Create( delegate { e = CalcE( a );  } ));

   while ( TRUE )
   {
      Uns tid = tasks.Id( Task.WaitAny( tasks.Active() ) );
      tasksComplete[tid] = TRUE;

      switch( tid )
      {
         case CC:
            if ( tasksComplete[DD] )
               tasks.Set( FF, Task.Create( delegate { f = CalcF( c, d );  } ));
            if ( tasksComplete[EE] )
               tasks.Set( GG, Task.Create( delegate { g = CalcG( c, e );  } ));
            break;

         case DD:
            if ( tasksComplete[DD] )
               tasks.Set( FF, Task.Create( delegate { f = CalcF( c, d );  } ));
            if ( tasksComplete[EE] )
               tasks.Set( HH, Task.Create( delegate { h = CalcH( c, e );  } ));
            break;

         case EE:
            if ( tasksComplete[CC] )
               tasks.Set( GG, Task.Create( delegate { g = CalcG( c, e );  } ));
            if ( tasksComplete[DD] )
               tasks.Set( HH, Task.Create( delegate { h = CalcH( d, e );  } ));
            break;
            
         case FF:
         case GG:
         case HH:
            if ( tasksComplete[FF] && tasksComplete[GG] && tasksComplete[HH] )
            {
               b = CalcB( f, g, h );
               return b;
            }
            break;
      }
   }
}      
        

Although this function is internally parallel, it is still a single entry point, sequential function. To improve this function further we need to make it reentrant and double buffered.

The reentrant double buffered solution is left as an exercise.

NB. With a multi-buffered, reentrant solution the sub-tasks are not strictly running in parallel as each function could be using different frames of data. In CDL we only use the term 'parallel' for data parallel tasks where we can use arrays of stores/methods etc. When running multi-buffered, reentrant functions (as in this example and in every other CLIP application) we use the term concurrent - A number of related and unrelated tasks running at the same time, but may have been started and end at different times.

CDL Solution

The CDL solution looks very similar to the original statement of the problem.

Click to enlarge

Simply giving each store and distributer a Buffer Depth/Reentrancy greater than 1 gives us a true Multi-buffered, reentrant solution, which is easily scalable to add more tasks.

Click to enlarge

 

© Connective Logic Systems Ltd. All Rights Reserved.